A computer system stores data in its memory. In order to do useful work, the computer system operates on and performs manipulations against this data. Ideally, a computer system would have a singular, indefinitely large and very fast memory, in which any particular data would be immediately available to the computer system. In practice this has not been possible because memory that is very fast is also very expensive.
Thus, computers typically have a hierarchy (or levels) of memory, each level of which has greater capacity than the preceding level but which is also slower with a less expensive per-unit cost. These levels of the hierarchy may form a subset of one another, that is, all data in one level may also be found in the level below, and all data in that lower level may be found in the one below it, and so on until we reach the bottom of the hierarchy. In order to minimize the performance penalty that the hierarchical memory structure introduces, it is desirable to store the most-frequently-used data in the fastest memory and the least-frequently-used data in the slowest memory.
Although a computer system might contain any number of levels of memory, consider the following example where the computer system contains two levels of memory:                1) a small, fast, and moderately expensive RAM (Random Access Memory)—often called main memory—that contains the most-frequently-used data; and        2) several large, slow, inexpensive disk drives that contain all the data in the computer system.        
When the computer system needs to allocate memory for data, it looks first in the main memory. If memory is not available in the main memory (no memory is free), the computer system must determine which data to remove from the main memory in order to make room for the data currently needed. For efficiency, data may be moved or migrated between levels of storage in units called pages. A page may be a fixed or variable length block of data that is moved as a unit. A page may also be called a page frame. The process of freeing pages in main memory to meet the demands of currently active work is called paging, page replacement, or page stealing.
The algorithm used to select which page is moved back through the levels (i.e., which page to steal or replace) is called the replacement algorithm. Often, a “least-recently-used” algorithm is used to govern movement of pages. That is, pages that have not recently been referenced are replaced first. Thus, if a page is not used for an extended period of time, it will migrate through the storage hierarchy to the slowest level. Hence, the most-recently-used data is contained in high-speed, main storage ready for immediate access, while less-frequently-used data migrates though the storage hierarchy toward the slower-speed storage, often called secondary storage.
Since a page may migrate across multiple physical addresses in the hierarchy of multiple storage devices, a technique called virtual addressing is often used, where a page has a virtual address, which does not change regardless of the physical address at which the page is currently stored. To handle the mapping of virtual addresses to physical addresses and migration of pages through the hierarchy, a page table is often used. The page table has an entry for each page and control information that is used to implement the replacement algorithm.
An example of control information is a reference bit, which indicates whether the page has been referenced or accessed. A typical page replacement algorithm uses the reference bit to determine whether to replace or steal a page. The page replacement algorithm replaces or steals the page if the page's reference bit is not set (is clear), and if the reference bit is set, the page replacement algorithm clears the reference bit without stealing the page. Since the reference bit is set once a page is accessed, each page scanned by the page replacement algorithm for the first time will have a reference bit that is set, so the page cannot be stolen. If none of the pages are allowed to be replaced or stolen, a second pass through the memory is required, replacing or stealing those pages whose reference bits continue to be clear. This additional pass through memory takes time, which hurts the performance of the computer system.
In order to increase performance, what is needed is a technique that allows a better selection of pages that can be stolen.